1. Technical Field
The present invention relates in general to a system and method for asynchronous linked data structure traversal. More particularly, the present invention relates to a system and method for asynchronously traversing a disjoint linked data structure using a handler while a main program executes concurrently.
2. Description of the Related Art
Computer systems typically use data structures for organizing and storing data. For example, a general data structure type may be an array, a file, a record, a table, or a tree. Data structures are designed to organize data that suits a specific purpose so that it is accessible and easily utilized. In computer programming, a data structure may be selected or designed to store data for the purpose of utilizing the data structure using various algorithms.
A linked list, or linked data structure, is one of the fundamental data structures used in computer programming. A linked data structure includes nodes whereby each node includes information (data) and “links” to other nodes. One type of linked data structure is a binary tree, which contains nodes that include data and two links to “child” nodes. A “parent” node's “left” link points to a child node whose data value is less than the parent node's data value, and the parent node's “right” link points to a child node whose data value is greater than the parent node's data value. Linked data structures allow a computer system to easily locate and process a particular node.
A challenge found is that linked data structures typically reside in non-contiguous memory. Meaning, node storage areas are typically spread over the computer system's memory area, especially nodes that are dynamically added. This causes a processor to use a call stack in order to track and locate node data locations.
Another challenge found is that a device traverses a linked data structure and processes the data in a serial manner, which results in data transfer latencies that bind a program's performance. With simple data structures whose element locations are known, a technique known as double-buffering (multi-buffering) may hide transfer latencies. However, when traversing linked data structures (e.g., binary trees), this kind of latency hiding technique is not effective.
Furthermore, a challenge found with traversing a linked data structure is that it may create problems with devices that have limited memory space. For example, if a limited memory space device traverses a large linked data structure, the call stack may become larger than the limited memory space and, therefore, the device may not be able to complete the linked data structure traversal.
What is needed, therefore, is a system and method to asynchronously traverse a linked data structure using a limited memory space.